//
// Created by Administrator on 2021/6/30.
//
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    int numWays(int n, vector<vector<int>> &relation, int k) {
        /**
         * 可以bfs dfs 或者dp
         * 按步来就可以
         */
        // 首先知道传递关系
        // 用二维矩阵或者hash记录
        vector<vector<bool>> transfer(n, vector<bool>(n, false));
        for (auto &x:relation) {
            transfer[x[0]][x[1]] = true;
        }
        // 队列,放入初始点
        queue<int> q;
        q.push(0);
        while (k > 0) {
            // 这一层有几个点
            auto levelNum = q.size();
            for (int i = 0; i < levelNum; ++i) {
                auto p = q.front();
                q.pop();
                for (int j = 0; j < n; ++j) {
                    if (transfer[p][j]) {
                        q.push(j);
                    }
                }
            }
            --k;
        }
        // 剩下的队列里有几个目标值
        int ans = 0;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p == n - 1) ++ans;
        }
        return ans;
    }
};

class Solution2 {
public:
    int numWays(int n, vector<vector<int>> &relation, int k) {
        /**
         * dp
         */
        vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
        dp[0][0] = 1;
        for (int i = 0; i < k; ++i) {
            for (auto &x:relation) {
                dp[i + 1][x[1]] += dp[i][x[0]];
            }
        }
        return dp[k][n - 1];

    }
};

int main() {
    vector<vector<int>> relation{{0, 2},
                                 {2, 1},
                                 {3, 4},
                                 {2, 3},
                                 {1, 4},
                                 {2, 0},
                                 {0, 4}};
    Solution2 solution;
    cout << solution.numWays(5, relation, 3);
    return 0;
}